package fag.core.geometry;

import java.util.ArrayList;
import java.util.List;

/**
* Classe ConvexHull.
* @author Thibault
*/

public class ConvexHull {
	
	/**
	 * Constructeur par default
	 */
	public ConvexHull(){}

	/**
	 * Méthode d'enveloppe convexe
	 * @param liste de vector2D
	 * @return une liste de Vector2D qui composent l'enveloppe convexe
	 */
	public static List<Vector2D> GrahamConvexHull(List<Vector2D> liste) {
	    List<Vector2D> lUpper = new ArrayList<Vector2D>();
	    List<Vector2D> lLower = new ArrayList<Vector2D>();
	    int n = liste.size();
	
	
	    // On débute avec les 2 premiers points de la liste de points
	        lUpper.add(liste.get(0));
	        lUpper.add(liste.get(1));
	
	        for(int i=2 ; i<n ; i++) {
	            lUpper.add(liste.get(i));
	
	            while(lUpper.size()>2 && Vector2D.det(lUpper.get(lUpper.size()-3), lUpper.get(lUpper.size()-2), lUpper.get(lUpper.size()-1))) {
	                lUpper.remove(lUpper.get(lUpper.size()-2));
	            }
	        }
	
	
	    // même raisonnement mais en partant de la fin de la liste
	        lLower.add(liste.get(n-1));
	        lLower.add(liste.get(n-2));
	
	        for(int i=n-1 ; i>=0 ; i--) {
	            lLower.add(liste.get(i));
	
	            while(lLower.size()>2 && Vector2D.det(lLower.get(lLower.size()-3), lLower.get(lLower.size()-2), lLower.get(lLower.size()-1))) {
	                lLower.remove(lLower.get(lLower.size()-2));
	            }
	        }
	
	        lLower.remove(0);
	        lLower.remove(lLower.size()-1);
	
	    
	    // Fusion des 2 listes (qui donnent les points de l'enveloppe convexe)
	    lUpper.addAll(lLower);
	    return lUpper;
	}
}